class Solution {
public:
    string intToRoman(int num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<pair<int, string> > lists;
        lists.push_back(make_pair(1, string("I")));
        lists.push_back(make_pair(4, string("IV")));
        lists.push_back(make_pair(5, string("V")));
        lists.push_back(make_pair(9, string("IX")));
        lists.push_back(make_pair(10, string("X")));
        lists.push_back(make_pair(40, string("XL")));
        lists.push_back(make_pair(50, string("L")));
        lists.push_back(make_pair(90, string("XC")));
        lists.push_back(make_pair(100, string("C")));
        lists.push_back(make_pair(400, string("CD")));
        lists.push_back(make_pair(500, string("D")));
        lists.push_back(make_pair(900, string("CM")));
        lists.push_back(make_pair(1000, string("M")));

        int cur = lists.size() - 1;
        string ans;

        while (num > 0) {
            while (lists[cur].first > num) {
                --cur;
            }
            ans += lists[cur].second;
            num -= lists[cur].first;
        }
        return ans;

    }
};
